package com.wuxuan.algorithm_homework.stackAndQueue;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 给定一个非负整数组，对于每个元素，找出它右边第一个比它大的元素。若没有最大的元素返回 -1.
 * 时间复杂度:O(n) ; 空间复杂度: O(n) ; 其中 n 为输入数组的长度
 */
public class Q5 {
    //关键逻辑精髓
    //1. 栈的作用
    //栈在这里的作用是帮助我们“记住”那些还没有找到右边比它们大的元素的索引。栈中的元素（索引）是按照递减顺序存储的，即栈顶元素对应的值是当前栈中最小的值。
    //2. 为什么用栈
    //单调栈：栈中的元素保持单调递减的顺序。当我们遇到一个比栈顶元素大的值时，这个值就是栈顶元素右边第一个比它大的值。
    //高效性：通过一次遍历，每个元素最多只会被压入和弹出栈一次，因此时间复杂度是 O(n)。
    //3. 关键步骤
    //初始化：
    //创建一个栈（Deque）来存储数组的索引。
    //创建一个结果数组 result，长度与输入数组相同，初始值为 -1。
    //遍历数组：
    //从左到右遍历数组，对于每个元素 nums[i]：
    //检查栈顶元素：如果栈不为空，且当前元素 nums[i] 大于栈顶元素对应的值 nums[stack.peekLast()]，说明找到了栈顶元素右边第一个比它大的元素。
    //更新结果数组：将栈顶元素对应的值设置为当前元素 nums[i]。
    //弹出栈顶元素：继续检查新的栈顶元素，直到栈为空或当前元素不再大于栈顶元素。
    //压入当前索引：将当前索引 i 压入栈中。
    //处理剩余元素：
    //如果遍历结束后栈中还有元素，这些元素对应的值在结果数组中已经初始化为 -1，表示它们右边没有比它们大的元素。

    //Eg:
    //[1, 3, 2 ,4, 5]
    //n = 5
    //for :
    // i = 0: stack为空，   stack.offerLast(0);  stack:| 0
    // i = 1: stack不为空， nums[0] < nums[1] 即 1 < 3 成立，故result[0] = nums[1] = 3 (而且将stack中的0元素移除，stack又变成空的了),然后执行stack.offerLast(1); stack: |1不为空
    // i = 2: stack不为空， nums[1] < nums[2] 即 3 < 2 不成立，故 stack.offerLast(2); stack: | 1 2
    // i = 3: stack不为空， nums[2] < nums[3] 即 2 < 4 成立，故result[2] = nums[3] = 4; stack | 1 ,继续进行while循环！！！ nums[1] < nums[3] 即 3 < 4，故result[1] = nums[3] = 4
    // 最后放入 stack.offerLast(3), stack: | 3
    // 目前 result:[3, 4, 4, ...]
    // i = 4: result[4] = -1 , stack不为空, nums[3] < nums[4] 即4 < 5 成立，故result[3] = nums[4] = 5,stack空，最后放入 stack.offerLast(4)，stack:| 4
    // 目前 result:[3, 4, 4, 5, -1]
    public int[] nextGreaterValue(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        Deque<Integer> stack = new LinkedList<>();
        int n = nums.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = -1;
            while (!stack.isEmpty() && nums[stack.peekLast()] < nums[i]) {
                result[stack.pollLast()] = nums[i];
            }
            stack.offerLast(i);
        }
        return result;
    }

    //测试一下
    public static void main(String[] args) {
        int[] nums = {1, 3, 2 ,4, 5};
        Q5 q5 = new Q5();
        int[] result = q5.nextGreaterValue(nums);
        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}
